package com.thghh.graph;

import java.util.*;

/**
 * 图
 *
 * @author pengzhikang
 * @date 2024/8/19 14:31
 * @since 1.0.0
 */
public class Graph2 {

    /** 顶点列表 */
    private Map<String, Vertex> vertexMap;

    public Graph2() {
        // 初始化顶点列表
        vertexMap = new HashMap<>();
    }

    /**
     * 获取顶点数
     *
     * @return int
     * @author pengzhikang
     * @date 2024/08/19 15:46
     */
    public int getNumOfVertex() {
        return vertexMap.size();
    }

    /**
     * 获取边数
     *
     * @return int
     * @author pengzhikang
     * @date 2024/08/19 15:46
     */
    public int getNumOfEdges() {
        int numOfEdges = 0;
        for (Vertex vertex : vertexMap.values()) {
            numOfEdges += vertex.getNumOfEdges();
        }
        return numOfEdges;
    }

    /**
     * 获取边的权重
     *
     * @param start 开始顶点
     * @param end   结束顶点
     * @return int
     * @author pengzhikang
     * @date 2024/08/19 15:46
     */
    public int getWeight(String start, String end) {
        Vertex vertex = vertexMap.get(start);
        if (vertex == null) {
            throw new IllegalArgumentException(start + "顶点不存在");
        }

        Edge edge = vertex.getEdge(end);
        return edge.getWeight();
    }

    /**
     * 插入顶点
     *
     * @param name 名称
     * @author pengzhikang
     * @date 2024/08/19 15:38
     */
    public Vertex addVertex(String name) {
        // 如果存在，直接返回
        if (vertexMap.containsKey(name)) {
            return vertexMap.get(name);
        }
        Vertex vertex = new Vertex(name);
        vertexMap.put(name, vertex);
        return vertex;
    }

    /**
     * 插入边
     *
     * @param start  开始
     * @param end    结束
     * @param weight 重量
     * @author pengzhikang
     * @date 2024/08/19 15:38
     */
    public void addEdge(String start, String end, int weight) {
        // 获取顶点，如果顶点不存在，则插入顶点
        Vertex vertex = addVertex(start);

        // 新建边
        Edge edge = new Edge(end, weight);
        vertex.addEdge(edge);
    }

    public void print() {
        for (Map.Entry<String, Vertex> entry : vertexMap.entrySet()) {
            Vertex vertex = entry.getValue();
            Edge edge = vertex.getEdge();
            while (edge != null) {
                System.out.println(vertex.getName() + "指向：" + edge.getName() + "权重是：" + edge.getWeight());
                edge = edge.getNext();
            }
        }
    }

    /**
     * 重置已访问
     *
     * @author pengzhikang
     * @date 2024/08/20 11:36
     */
    public void resetVisited() {
        for (Vertex vertex : vertexMap.values()) {
            vertex.setVisited(false);
        }
    }

    /**
     * 深度优先搜索，后进先出（LIFO）
     *
     * @param start 开始
     * @param end   结束
     * @return {@link List }<{@link String }>
     * @author pengzhikang
     * @date 2024/08/20 11:24
     */
    public List<String> dfs(String start, String end) {
        if (!vertexMap.containsKey(start) || !vertexMap.containsKey(end)) {
            throw new  IllegalArgumentException("start or end not exist");
        }
        List<String> result = new ArrayList<>();

        Deque<Vertex> stack = new ArrayDeque<>();
        // 获取起始顶点
        stack.push(this.vertexMap.get(start));

        while(!stack.isEmpty()) {
            Vertex vertex = stack.pop();
            // 判断是否访问过
            if (!vertex.isVisited()) {
                vertex.setVisited(true);
                result.add(vertex.getName());
                Edge edge = vertex.getEdge();
                while (edge != null) {
                    Vertex nextVertex = this.vertexMap.get(edge.getName());
                    if (!nextVertex.isVisited()) {
                        stack.push(nextVertex);
                    }
                    edge = edge.getNext();
                }
            }
        }

        return result;
    }

    /**
     * 广度优先遍历，先进先出（FIFO）
     *
     * @param start 开始
     * @param end   结束
     * @return {@link List }<{@link String }>
     * @author pengzhikang
     * @date 2024/08/20 11:23
     */
    public List<String> bfs(String start, String end) {
        if (!vertexMap.containsKey(start) || !vertexMap.containsKey(end)) {
            throw new  IllegalArgumentException("start or end not exist");
        }
        List<String> result = new ArrayList<>();

        Deque<Vertex> stack = new ArrayDeque<>();
        // 获取起始顶点
        stack.add(this.vertexMap.get(start));

        while(!stack.isEmpty()) {
            Vertex vertex = stack.remove();
            // 判断是否访问过
            if (!vertex.isVisited()) {
                vertex.setVisited(true);
                result.add(vertex.getName());
                Edge edge = vertex.getEdge();
                while (edge != null) {
                    Vertex nextVertex = this.vertexMap.get(edge.getName());
                    if (!nextVertex.isVisited()) {
                        stack.add(nextVertex);
                    }
                    edge = edge.getNext();
                }
            }
        }

        return result;
    }

}
